/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 21:59
 */


// 【模板】01背包
// 1）求这个背包至多能装多大价值的物品？
//（2）若背包恰好装满，求至多能装多大价值的物品？

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int v=in.nextInt();
        int[] arrV=new int[n+1];
        int[] arrW=new int[n+1];
        // 注意 hasNext 和 hasNextLine 的区别
        for(int i=1;i<=n;i++) { // 注意 while 处理多个 case
            arrV[i] = in.nextInt();
            arrW[i] = in.nextInt();
            // System.out.println(a + b);
        }

        //输入结束

        func(arrV,arrW,n+1,v+1);
    }

    public static void func(int[] arrV,int[] arrW,int n,int v){
        //动态规划
        //创建dp数组

        int[][] dp1=new int[n][v];

        int[][] dp2=new int[n][v];
        //把dp2的第一行从1下标开始都置为-1
        for(int i=1;i<v;i++){
            //约定dp数组中的值为 -1 表示不存在合适的情况
            dp2[0][i]=-1;
        }

        for(int i=1;i<n;i++){
            //i是有几个物品
            for(int j=1;j<v;j++){
                //j相当于是容量

                //同时处理dp1和dp2
                //先处理：dp1
                //第i个物品是否装进背包里面
                //装进背包里面
                // 把第i个物品放进背包中的情况：
                //对应的状态转移方程：a1=dp[i-1][j-vw[i-1][0]]+vw[i-1][1];
                int a1=0;
                if(j-arrV[i]>=0){
                    a1=dp1[i-1][j-arrV[i]]+arrW[i];
                }

                //不装进背包里面
                //对应的状态转移方程：a2=dp[i-1][j];
                int a2=dp1[i-1][j];
                dp1[i][j]=a1>a2?a1:a2;

                //再处理：dp2
                //第i个物品是否装进背包里面
                //装进背包里面
                int b1=-1;//b1存在，则后面的操作会改变它的值，若不存在，则理应为-1(b1的这个初始值也很重要的)
                //约定dp数组中的值为 -1 表示不存在合适的情况
                if(j-arrV[i]>=0 && dp2[i-1][j-arrV[i]]!=-1){
                    b1=dp2[i-1][j-arrV[i]]+arrW[i];
                }
                //不装进背包里面
                int b2=dp2[i-1][j];

                dp2[i][j]=b1>b2?b1:b2;
            }

        }



        System.out.println(dp1[n-1][v-1]);
        if(dp2[n-1][v-1]==-1){
            //题目要求，不能打印-1，若是不存在就打印0
            System.out.println(0);
        }else{
            System.out.println(dp2[n-1][v-1]);
        }


    }
}























